/*
提交链接：https://leetcode.cn/problems/number-of-digit-one/submissions/572344385
233. 数字 1 的个数-困难
完成日期：2024/10/13
数位DP
*/

class Solution {
public:
    int countDigitOne(int n) {
        // 将 n 转换为字符串方便处理
        std::string numStr = std::to_string(n);
        int len = numStr.size();
        // dp 数组，初始化为 -1 表示未计算
        memset(dp, -1, sizeof(dp));
        return dfs(numStr, 0, 0, true, false);
    }
private:
    int dp[20][20][2][2]; // dp[pos][count][isLimit][isNum]
    int dfs(const std::string &numStr, int pos, int count, bool isLimit, bool isNum) {
        // 当处理到最后一位时，返回已计算的 1 的数量
        if (pos == numStr.size()) {
            return count;
        }
        // 如果已经计算过，直接返回结果
        if (dp[pos][count][isLimit][isNum] != -1) {
            return dp[pos][count][isLimit][isNum];
        }
        int res = 0;
        int up = isLimit ? (numStr[pos] - '0') : 9; // 当前位的上界
        for (int digit = 0; digit <= up; ++digit) {
            // 更新下一位的状态
            res += dfs(numStr, pos + 1,
                       count + (digit == 1 ? 1 : 0), // 如果当前位是 1，增加计数
                       isLimit && (digit == up), // 更新是否受限
                       isNum || (digit > 0)); // 更新是否开始形成数字
        }
        // 记录并返回结果
        return dp[pos][count][isLimit][isNum] = res;
    }
};